package medium

/*
时间复杂度：O(N)
空间复杂度：O(1)

解：从结果推到过程的思想，结果是所有的1都连续排列在一起，所以可以计算出所有1的数量k，然后控制窗口大小为k；
通过遍历k的位置（即滑动窗口），动态计算窗口内1的总数，求1最多的次数即可，因为1最多，则需要将0与1进行位置交换的次数最小
*/

func minSwaps(data []int) int {
	n := len(data)
	totalOne := 0
	// 先计算所有的1的数量
	for _, v := range data {
		if v == 1 {
			totalOne++
		}
	}

	// 计算初试窗口1的数量,初始窗口设置为1的总数
	countOne := 0
	for i := 0; i < totalOne; i++ {
		countOne += data[i]
	}

	// 滑动窗口
	maxCount := countOne
	for i := totalOne; i < n; i++ {
		// 向右滑动窗口，添加右边界元素，减去左边界元素
		countOne += data[i] - data[i-totalOne]
		// 要使操作次数最小，则窗口内的1的数量要最多
		if maxCount < countOne {
			maxCount = countOne
		}
	}
	return totalOne - maxCount
}
